1. Field of the Invention
The present invention relates to a method of re-mapping a flash memory, and more particularly, to a method of re-mapping a flash memory, which can minimize the number of times the flash memory is accessed and can enable the entire area of the flash memory to be evenly used.
2. Description of the Related Art
In general, home appliances, communications devices, and embedded systems, such as set-top boxes, use non-volatile memories such as storage devices for storing and processing data.
Flash memories are one type of non-volatile memory, in which data can be electrically erased and overwritten. Flash memories are suitable for portable devices because they consume less power than magnetic disc memory-based storage mediums, are as accessible as hard discs, and are compact-sized.
Due to the hardware characteristics of flash memories, data recorded on a flash memory is erased in units of blocks, unlike in the conventional random access memory (RAM), nonvolatile storage medium or magnetic storage medium.
In other words, in the flash memories, data is recorded on a sector as a logical operation unit of a host while data recorded on the sector is erased by deleting the overall blocks containing the sector.
Since a unit in which data is recorded on a flash memory is different from a unit in which data is erased from the flash memory, the performance of the flash memory may deteriorate.
In order to prevent the performance of the flash memory from deteriorating for this reason, logical addresses and physical addresses have been suggested.
In other words, to perform data reading or writing operations, predetermined logical addresses are changed into physical addresses of the flash memory through various types of algorithms. In this case, the performance of the flash memory can be maximized by performing mapping in consideration of physical conditions of the flash memory.
A flash translation layer is software that helps the use of the flash memory as a block device, and generally supports a re-mapping method for efficiently managing the flash memory.
Here, the re-mapping method enables management of mapping information on the relationships between logical block numbers (LBNs) and physical block numbers (PBNs) of given data. By doing so, data recorded in the flash memory is always accessible with the same logical block number (LBN) even though a pertinent PBN changes.
In other words, referring to FIGS. 1A and 1B, when a request for reading or writing data using a predetermined logic block number (LBN) is issued, the predetermined LBN is mapped to a logical unit number (LUN) with reference to an LBN-to-LUN mapping table and is also mapped to a physical unit number (PUN) with reference to an LUN-to-PUN mapping table.
A physical unit will be briefly explained below. Referring to FIGS. 2A and 2B, physical units 10 and 20 include erase unit headers (EUHs) 11 and 21, block allocation maps (BAMs) 12 and 22, and sets 13 and 23 of blocks where data is stored, respectively.
The EUHs 11 and 21 store various metadata on the respective physical units. The BAMs 12 and 22 may be recorded as at least one block under the respective EUHs.
In addition, the BAMs 12 and 22 may also be recorded as blocks in a space such as a spare array of a NAND flash memory.
The BAMs 12 and 22 may store information on blocks of the respective physical units, such as LBNs and state information of the blocks of the respective physical units.
Therefore, when a request for writing data to a predetermined logic block is issued, a PUN corresponding to the predetermined logic block is obtained, and then data is written to a recordable block of a BAM of the PUN. Thereafter, the address of the predetermined logic block is recorded in the BAM of the PUN.
For example, as shown in FIGS. 3A and 3B, when a request for writing data to logic block 3 is issued twice, data is written to a fourth block of a BAM of a PUN, which is an empty block, in response to the second request, and the serial number of logic block 3 is recorded in the fourth block of the BAM.
Data can be read from a predetermined logic block in almost the same manner as data is written to the predetermined logic block.
A lap count is adopted to indicate block state information, which is used for recovering data in case of errors.
In other words, a predetermined block may exist in a free state (1111), a valid state, or a deleted state (0000). The valid state is classified into s0 (1110), s1 (1100), and s2 (1000) that satisfy the following recursive relationships:s0<s1, s1<s2, and s2<s0where < indicates the temporal order of two states.
Therefore, if an error occurs in current data, the current data can be recovered using previous or subsequent data.
For example, supposing that an error occurs in fifth data or data subsequent to the fifth data, there are two valid data, the lap counts of which are 1110 and 1100, respectively, as shown in FIG. 4.
Here, since the lap count value 1110 is ahead of the lap count value 1100, righthand data is deleted if a subsequent data-based data recovery method is adopted.
In a flash memory, a logic unit is mapped to a physical unit one by one. In a case where sectors of a predetermined logic unit are frequently updated or in a case where the predetermined logic unit has no empty sectors, an empty physical unit is allocated to the predetermined logic unit, and valid sectors of the predetermined logic unit are copied to the empty physical unit.
Since physical units of a flash memory can be erased only a limited number of times, the physical units of the flash memory should be evenly used in order to increase the durability of the flash memory.
However, there is a clear limit in increasing the durability of a flash memory because, conventionally, empty physical units are used in an arbitrary manner regardless of their respective erasabilities.
In addition, the allocation of an empty physical unit to a logic unit requires additional operations to write data to a flash memory, thus decreasing the efficiency of writing data to the flash memory.